import java.util.Arrays;

/**
 * 132. 分割回文串 II
 * https://leetcode-cn.com/problems/palindrome-partitioning-ii/
 */
public class Solutions_132 {
    public static void main(String[] args) {
//        String s = "aab";  // output: 1
//        String s = "baab";  // output: 0
        String s = "leet";  // output: 2
//        String s = "a";  // output: 0
//        String s = "ab";  // output: 1

        int result = minCut(s);
        System.out.println(result);
    }

    /**
     * 解题思路：动态规划
     * 以 aab 为例
     * 字符串 a 不需要切割 dp[0] = 0
     * 字符串 aa 不需要切割 dp[1] = 0
     * 字符串 aab 需要切割，切割方案：
     * 在 b 之前，第 2 个 a 之后切割 1 次
     * 故 dp[2] = dp[1] + 1
     */
    public static int minCut(String s) {
        char[] arr = s.toCharArray();
        int len = arr.length;
        // dp[2] = 1，表示区间为 [0, 2] 的字符串最少需要切割 1 次，使每个子串都是回文
        int[] dp = new int[len];
        // 设置初始值
        Arrays.fill(dp, len - 1);

        for (int i = 0; i < len; i++) {
            // aba 结构回文串（长度为奇数）
            palindromic(i, i, arr, dp);
            // abba 结构回文串（长度为偶数）
            palindromic(i, i + 1, arr, dp);
        }
        return dp[len - 1];
    }

    public static void palindromic(int left, int right, char[] arr, int[] dp) {
        while (left >= 0 && right < arr.length && arr[left] == arr[right]) {
            int cur = 0;
            if (left > 0) {
                // 需要在索引 left 后切割 1 次，才能保证 [left, right] 的子串是一个回文串
                cur = dp[left - 1] + 1;
            }
            // 比较得到最优方案
            dp[right] = Math.min(dp[right], cur);

            // 左右指针向两侧扩展
            left --;
            right ++;
        }
    }
}
